# -*- coding: utf-8 -*-
# 给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵
# 示例:
# 输入: 3
# 输出:
# [
#  [ 1, 2, 3 ],
#  [ 8, 9, 4 ],
#  [ 7, 6, 5 ]
# ]









# 解题思路：
#  3 * 3 == 3 + 2 + 2 + 1 + 1
#  4 * 4 == 4 + 3 + 3 + 2 + 2 + 1 + 1
#  刚好和一圈一圈剥洋葱时走的步数相同
#  以3为例
#  左3 下2 右2 上1 左1
class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        direction = [[0,1], [1,0], [0,-1], [-1,0]];
        di = 0;

        count = 0;
        r = 0;
        c = -1;

        rtn = [[0] * n for _ in range(n)];

        for i in range(2 * n - 2, -1, -1):
            step = i // 2 + 1;
            d = direction[di];
            for _ in range(step):
                r += d[0];
                c += d[1];
                count += 1;
                rtn[r][c] = count;
            di = (di + 1) % 4;

        return rtn;






t = Solution();
print t.generateMatrix(3);